#include <bits/stdc++.h>
using namespace std;
class Water_Tank {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        int max = 0;
        int maxindex = -1;
        int water = 0;
        int begin = 0;
        int end = len - 1;
        for (int i = 0; i < len; i++) {//获取数组的最高值
            if (max < height[i]) {
                max = height[i];
                maxindex = i;
            }
        }
        water = water + leftpartialwater(height, begin, maxindex, max);//计算最高值左边的雨水量
        water = water + rightpartialwater(height, maxindex, end, max);//计算最高值右边的雨水量
        return water;
    }
    int leftpartialwater(vector<int> &heights, int begin, int end, int max) {//计算左边的存水量
        int curwater = 0;
        if (begin >= end) {
            curwater = 0;
        } else {
            int curmax = 0;
            int curmaxindex = -1;
            for (int i = begin; i < end; i++) {//查找最大值左边的其他元素的最大值
                if (curmax <= heights[i]) {
                    curmax = heights[i];
                    curmaxindex = i;
                }
            }
            curwater = (end - curmaxindex - 1) * curmax;
            int other = 0;
            for (int j = curmaxindex + 1; j < end; j++) {
                other = other + heights[j];
            }
            curwater = curwater - other;//计算之前的最大值到当前求出的最大值之间的存水量
            curwater = curwater + leftpartialwater(heights, begin, curmaxindex, curmax);//递归，求当前的最大值到下一个最大值之间的存水量
        }
        return curwater;
    }
    int rightpartialwater(vector<int> &heights, int begin, int end, int max) {
        int curwater = 0;
        if (begin >= end) {
            curwater = 0;
        } else {
            int curmax = 0;
            int curmaxindex = - 1;
            for (int i = begin + 1; i <= end; i++) {
                if (curmax <= heights[i]) {
                    curmax = heights[i];
                    curmaxindex = i;
                }
            }
            curwater = (curmaxindex- begin - 1) * curmax;
            int other = 0;
            for (int j = begin + 1; j < curmaxindex; j++) {
                other = other + heights[j];
            }
            curwater = curwater - other;//计算之前的最大值到当前求出的最大值之间的存水量
            curwater = curwater + rightpartialwater(heights, curmaxindex, end, curmax);//递归，求当前的最大值到下一个最大值之间的存水量
        }
        return curwater;
    }
};
